package com.heima.datastructure.hashtable;
import com.google.common.hash.Hashing;
import java.nio.charset.StandardCharsets;
import java.util.Arrays;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * <h2>哈希表</h2>
 * <p>给每份数据分配一个编号，放入表格(数组)</p>
 * <p>创建编号与表格索引的关系，将来可以通过编号快速查询数据</p>
 * <ul>
 *     <li>理想情况：编号都唯一，数组能容纳所有内容</li>
 *     <li>实际情况：不能说为了容纳所有内容就创建一个超大的数组，编号也有可能重复</li>
 * </ul>
 * <p>解决</p>
 * <ul>
 *     <li>有限长度的数组，用【拉链】方法容纳更多的数据，每个数组元素接一个链表</li>
 *     <li>允许编号适当重复，通过数据自身来进行区分</li>
 * </ul>
 * <p>本例实现的哈希值是int类型，通过哈希值对数组长度取模运算建立哈希值与索引之间的关系</p>
 * <br>
 * <h2>哈希算法</h2>
 * <ul>
 *     <li><p>将输入数据（通常是可变大小的数据）转换成固定大小的数据输出（称为哈希值或哈希码）的算法。哈希算法常用于数据检索、密码安全、数据完整性验证等领域。</p></li>
 *     <li><p>常见哈希算法有MD5，SHA-1，SHA-2，SHA-3，CRC32，BLAKE2，MurmurHash</p></li>
 *     <li><p>可以理解为哈希算法就是给任意对象分配一个编号的过程，其中编号是一个有限范围内的数字，所以要保证均匀的分配编号，尽量不要重复</p></li>
 *     <li><p>Object的hashCode方法是按照对象实例来进行分配哈希码，同一个类的不同实例对象的哈希码不同</p></li>
 *     <li><p>String重写了hashCode方法，String是按照字符串中每个字符的ASCII编码拼接而成的，拼接的方法是每个字符乘以一个权重加起来，这里权重采用的质数31^n，选用31的原因是他和32(2^5)很近，可以用移位运算优化性能</p></li>
 *     <li><p>MurmurHash属于第二代哈希算法，属于非加密的散列算法，优于传统的其他哈希算法，计算速度更快，不同平台上能得到相同的哈希值，所以这种哈希函数常用于快速查找、缓存键值以及分布式系统中的数据分区等场景。</p></li>
 *     <li><p>哈希冲突（Hash Collision），也称为哈希碰撞，指的是在使用哈希表存储数据时，两个或多个不同的键（Key）被哈希函数映射到了同一个哈希表的位置上，调用Object的hashcode也会发生哈希碰撞</p></li>
 * </ul>
 *
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/24 11:30
 */
public class HashTable<K, V> {
    /*
     * 一、满足数组长度为2^n的时候有以下结论：
     * 1、hush & (table.length - 1) == hush % table.length
     * 原因：
     * （1）因为table.length == 2^n，所以取余就相当于右移n位，截取移出去的数作为余数
     * （2）(table.length - 1)就是n个1，所以hush & (table.length - 1)就是保留hush的最后n位，其他舍弃
     * 2、旧链表拆分为两条链表，区分规则：hush & 旧链表长度 == 0 （不会变），hush & 旧链表长度 != 0 （会变）
     * 原因：
     * （1）旧链表的索引值都是小于旧链表长度的，索引为最后n位，而扩容后，变成原来的一倍，索引为最后n + 1位
     * （2）后n位的排列组合不变，就看新增的一位，要么为1，要么为0，
     * （3）新增位为0的索引值，就是新链表的不会变的索引值，新增位为1的索引值，就是新链表的新的索引值
     * （4）怎么变成新索引呢，原始索引左边新增一个1就可以，也就是加上原数组长度
     * 3、高低位异或减少哈希碰撞
     * 原因：
     * （1）哈希值和索引的对应关系是模运算，数组长度是2^n，索引实际就是哈希值的低位，所以当数组较小，很容易算出相同的索引
     * （2）但是可以通过异或操作，让低位综合高位的信息，让相似的哈希值（例如低位相同）变得更加不同，也就让生成的索引更加的分散
     * （3）哈希碰撞的概率也就下降了
     * 二、选用数组长度时其实也可以不用2的次幂
     * （1）例如老版本的jdk的HashTable实现，默认容量是11，一个质数
     * （2）用质数去算索引，对应的分散性更好，但是运算耗时更多
     * （3）分散性更好的原因是，如果非质数，那么一定是某个数的倍数，那么肯定有一部分的数据相似，哈希碰撞的概率就会上升，而质数就不会
     * （4）而用2^n长度的数组，可以减少计算耗时，但是生成的索引不那么分散，所以需要高位低位异或提高分散性
     * 三、在现在的HashMap中，链表长度唱过8的时候会转换为红黑树
     * （1）可以参考将340w个单词存入哈希表中，最长的链表长度也就6，而且只有两个，所以链表长度到8的时候，数据量已经很大了，可以说很少会出现这种情况
     * （2）但是为了防止恶意的攻击，一直往哈希表中放入哈希冲突的数据，就会导致哈希表性能大幅降低，严重拖累服务器
     * （3）所以过长就会转成红黑树（一种自平衡的二叉搜索树），提升查找效率到对数级，性能略优于AVL树，相当于一种兜底方案
     * （4）不直接用红黑树的原因是因为链表的长度多数情况下比较短，红黑树的插入、删除需要平衡、重构树，会有额外维护树结构的开销
     * 四、哈希算法：也就是为每份数据分配一个编号，这个编号能体现出该数据的特性，也就是摘取数据的一部分，也叫摘要算法，或者散列算法
     * （1）因为只取一部分，所以多种数据生成的哈希值可能会相同，也就是哈希冲突，哈希碰撞也可以指哈希表存放数据时有两个不同的数据被分配到同一个索引位置
     * （2）导致这种冲突的根本原因就是摘要出来的数据比较大概率相同，而哈希算法就需要优化，降低摘要的数据相同的概率
     * （3）一种思路就是质数，可以减少模式重复，意思就是打破周期性的冲突，有着好的分散性和均匀性
     * （4）另一种思路就是高低位异或，让低位可以更多的包含整个数据的信息，那么就分散
     */
    private Entry<K, V>[] table; // 哈希表数组用于存放每列链表的头节点，多态

    private int size; // 哈希表中元素的个数，不是指的数组的元素个数，而是指的所有元素个数

    private static final int DEFAULT_CAPACITY = 16; // 默认初始化容量，要设置为2的次幂，方便进行模运算，效率高

    private static final float LOAD_FACTOR = 0.75f; // 负载因子，默认为0.75  16 * 0.75 = 12 阈值，哈希表中实际存放的键值数量，包括链表节点 / 数组容量

    private int threshold; // 阈值，超过该值，需要扩容，这里的阈值指的是哈希表中实际存放的键值数量，包括链表节点

    /**
     * 无参构造，默认初始化容量是16
     */
    @SuppressWarnings("unchecked")
    public HashTable() {
        this.table = new Entry[DEFAULT_CAPACITY];
        this.threshold = (int) (DEFAULT_CAPACITY * LOAD_FACTOR);
    }

    /**
     * 有参构造，指定初始化容量
     *
     * @param capacity 指定容量
     */
    @SuppressWarnings("unchecked")
    public HashTable(int capacity) {
        // capacity <= 0
        if (capacity <= 0) {
            throw new IllegalArgumentException("参数不合法");
        }
        // 判断是否为2的次幂
        if (!is2N(capacity)) {
            capacity = nearest2N(capacity);
        }
        // 初始化容量
        this.table = new Entry[capacity];
        this.threshold = (int) (capacity * LOAD_FACTOR);
    }

    /**
     * 哈希表的节点类
     *
     * @param <K> 键的数据类型
     * @param <V> 值的数据类型
     */
    static class Entry<K, V> {
        int hash; // 哈希值
        K key; // 键
        V value; // 值
        Entry<K, V> next; // 下一个节点，默认初始化为null

        Entry(int hash, K key, V value) {
            this.hash = hash;
            this.key = key;
            this.value = value;
        }
    }

    /* 电脑中都是用补码存的数字
     * 1、有符号右移运算：>>
     *   （1）如果该数是正数，则右移n位，最高位补0，才不会影响数值
     *       0000 0000 0000 0000 0000 0000 0000 0101 >> 2
     *     = 0000 0000 0000 0000 0000 0000 0000 0001
     *   （2）如果该数是负数，则右移n位，最高位补1，才不会影响数值
     *       1111 1111 1111 1111 1111 1111 1111 1011 >> 2
     *     = 1111 1111 1111 1111 1111 1111 1111 1110
     *   （3）所以又叫算数右移
     * 2、有符号左移运算：<<
     *   （1）如果该数是正数，则左移n位，最低位补0，才不会影响数值
     *       0000 0000 0000 0000 0000 0000 0000 0101 << 2
     *     = 0000 0000 0000 0000 0000 0000 0001 0100
     *   （2）如果该数是负数，则左移n位，最低位补0，才不会影响数值
     *       1111 1111 1111 1111 1111 1111 1111 1011 << 2
     *     = 1111 1111 1111 1111 1111 1111 1110 1100
     *   （3）所以又叫算数左移
     * 3、无符号右移运算：>>>
     *   （1）如果该数是正数，则右移n位，最高位补0
     *       0000 0000 0000 0000 0000 0000 0000 0101 >> 2
     *     = 0000 0000 0000 0000 0000 0000 0000 0001
     *   （2）如果该数是负数，则右移n位，最高位补0
     *       1111 1111 1111 1111 1111 1111 1111 1011 >> 2
     *     = 0011 1111 1111 1111 1111 1111 1111 1110
     * 4、Java中没有所谓的“无符号左移”<<<，只有左移运算：<<
     */
    @SuppressWarnings("all")
    private static int hash(Object key){
        // String的话还可以用MurmurHash再优化一下
        if (key instanceof String s){
            return Hashing.murmur3_32().hashString(s, StandardCharsets.UTF_8).asInt();
        }
        int hash = key.hashCode();
        // 这里的意思是保留高16位，低16位需要综合高16位的信息，再返回，无论正负，最高位填0，所以用的是无符号右移
        // 将hash的高16位和低16位的信息混合起来，这样得到的hash值就比较分散了，哈希冲突减少
        // 如果不做处理，那么将Object生成的hash值转化为索引的时候，如果说当前哈希表的长度比较小，而且是2^n，
        // 也就是说转化出来的索引就是截取Object生成的hash值低n位，n越小，索引重复的概率越高，越容易产生哈希碰撞
        // 像这样优化的前提：1、哈希表长度为2的次幂
        return hash ^ (hash >>> 16);
    }

    /**
     * 判断是否为2的次幂
     *
     * @param number 待判断的数字，整数
     * @return true：是2的次幂，false：不是2的次幂
     */
    private static boolean is2N(int number) {
        return number > 0 && (number & (number - 1)) == 0;
    }

    /**
     * 获取大于等于number的最接近的2的次幂
     *
     * @param number 待判断的数字，整数
     * @return 找到的2的次幂
     */
    private static int nearest2N(int number) {
        number |= number >> 1;
        number |= number >> 2;
        number |= number >> 4;
        number |= number >> 8;
        number |= number >> 16;
        return number + 1;
    }

    /**
     * 根据键获取值，用Object类生产key的hash值
     *
     * @param key 键
     * @return 值
     */
    V getHashFromObject(K key) {
        // 用Object类的hashCode方法生成的哈希值
        return get(key.hashCode(), key);
    }

    /**
     * 根据哈希值和键获取值
     *
     * @param hash 哈希值
     * @param key  键
     * @return 值
     */
    V get(int hash, K key) {
        // 根据哈希值获取索引
        int index = hash & (table.length - 1);
        // 获取索引对应的链表头节点
        Entry<K, V> node = table[index];
        // 头节点为空，直接返回
        if (node == null) {
            return null;
        }
        // 头节点非空，遍历链表，找到对应key的节点
        else {
            // 遍历链表，找到对应key的节点
            while (node != null) {
                // 找到则返回
                if (node.key.equals(key)) {
                    return node.value;
                }
                node = node.next;
            }
            // 遍历完链表，未找到，返回null
            return null;
        }
    }

    /**
     * 获取键值，用hash方法生成哈希值
     * @param key 键
     * @return  值
     */
    public V get (K key){
        return get(hash(key), key);
    }

    /**
     * 插入键值，用Object类生产key的hash值
     *
     * @param key   键
     * @param value 值
     */
    void putHashFromObject(K key, V value) {
        // 用Object类的hashCode方法生成的哈希值，选择key生成hash值是因为key保证唯一
        put(key.hashCode(), key, value);
    }

    /**
     * 根据哈希值和键插入值
     *
     * @param hash  哈希值
     * @param key   键
     * @param value 值
     */
    void put(int hash, K key, V value) {
        // 根据哈希值获取索引
        int index = hash & (table.length - 1);
        // 获取索引对应的链表头节点
        Entry<K, V> entry = table[index];
        // 头节点为空，直接插入，返回
        if (entry == null) {
            table[index] = new Entry<>(hash, key, value);
            size++;
        }
        // 头节点非空，遍历链表，找到对应key的节点
        else {
            while (true) {
                // 找到则更新值并返回
                if (entry.key.equals(key)) {
                    entry.value = value;
                    break;
                }
                // 没有下一个节点，遍历完链表，未找到，插入
                else if (entry.next == null) {
                    entry.next = new Entry<>(hash, key, value);
                    size++;
                    break;
                }
                // 当前节点key不相等，并且还有下一个节点，继续遍历
                else {
                    entry = entry.next;
                }
            }
        }
        if (size > threshold) {
            resize();
        }
    }

    /**
     * 插入键值，用hash方法生成哈希值
     * @param key  键
     * @param value 值
     */
    public void put (K key, V value){
        put(hash(key), key, value);
    }

    /**
     * 扩容，扩容到原来的一倍，也就是 * 2
     * <br><br>
     * <p><strong>一个数组元素对应链表拆分并移动到新数组规律</strong></p>
     * <ol>
     *     <li>一个链表最多拆成两个</li>
     *     <li>hush & table.length == 0 的一组</li>
     *     <li>hush & table.length != 0 的另一组</li>
     *                                        p<br>
     *     0 -> 8 -> 16 -> 24 -> 32 -> 40 -> 48 -> null
     *     <br>
     *                       a<br>
     *     0 -> 16 -> 32 -> 48 ->null
     *     <br>
     *                 b<br>
     *     8 -> 24 -> 40 -> null
     *     <li>拆分后，放到新数组中的索引规律：a：原始索引，b：原始索引 + 原始数组长度</li>
     * </ol>
     */
    @SuppressWarnings("unchecked")
    private void resize() {
        // 新建一个数组，容量为原数组的两倍
        Entry<K, V>[] newTable = new Entry[table.length << 1];
        // 遍历原数组，将链表拆分为两个新链表，并移动到新数组
        for (int i = 0; i < table.length; i++) {
            Entry<K, V> entry = table[i]; // 获取当前遍历到的链表头节点
            Entry<K, V> aTail = null; // 链表a的尾节点，指的是链表中最后一个节点
            Entry<K, V> bTail = null; // 链表b的尾节点，指的是链表中最后一个节点
            Entry<K, V> aHead = null; // 链表a的头节点，指的是链表中第一个节点
            Entry<K, V> bHead = null; // 链表b的头节点，指的是链表中第一个节点
            // 当前遍历到的链表不为空，遍历链表，拆分链表，并移动到新数组
            if (entry != null) {
                while (entry != null) {
                    // 判断当前节点的哈希值是否在原数组长度范围内，如果是，则放入链表a，
                    if ((entry.hash & table.length) == 0) {
                        if (aTail != null) {
                            aTail.next = entry;
                        } else {
                            aHead = entry;
                        }
                        aTail = entry;
                    }
                    // 否则放入链表b
                    else {
                        if (bTail != null) {
                            bTail.next = entry;
                        } else {
                            bHead = entry;
                        }
                        bTail = entry;
                    }
                    entry = entry.next;
                }
                // 链表a不为空，则将其尾指针的next指向null，并移动到新数组
                if (aHead != null) {
                    aTail.next = null;
                    newTable[i] = aHead;
                }
                // 链表b不为空，则将其尾指针的next指向null，并移动到新数组
                if (bHead != null) {
                    bTail.next = null;
                    newTable[i + table.length] = bHead;
                }
            }
        }
        // 更新数组和阈值
        table = newTable;
        threshold = (int) (newTable.length * LOAD_FACTOR);
    }

    /**
     * 根据键删除元素并返回删除元素的值，用Object类生成key的hash值
     *
     * @param key 键
     * @return 值
     */
    V removeHashFromObject(K key) {
        // 用Object类的hashCode方法生成的哈希值，选择key生成hash值是因为key保证唯一
        return remove(key.hashCode(), key);
    }

    /**
     * 根据哈希值和键删除元素并返回删除元素的值
     *
     * @param hash 哈希值
     * @param key  键
     * @return 删除元素的值
     */
    V remove(int hash, K key) {
        // 根据哈希值获取索引
        int index = hash & (table.length - 1);
        // 获取索引对应的链表头节点
        Entry<K, V> entry = table[index];
        // 用于记录找到节点的前一个节点
        Entry<K, V> prev = null;
        // 头节点为空，直接返回
        if (entry == null) {
            return null;
        }
        // 头节点非空，遍历链表，找到对应key的节点
        while (entry != null) {
            // 找到了，删除并返回
            if (entry.key.equals(key)) {
                // 情况一：删除节点是头节点
                if (prev == null) {
                    table[index] = entry.next;
                }
                // 情况二：删除节点不是头节点
                else {
                    prev.next = entry.next;
                }
                // 元素个数减一
                size--;
                return entry.value;
            }
            prev = entry;
            entry = entry.next;
        }
        // 遍历完链表，未找到，返回null
        return null;
    }

    /**
     * 删除元素，用hash方法生成哈希值
     * @param key 键
     * @return 删除元素的值
     */
    public V remove(K key){
        return remove(hash(key), key);
    }

    /**
     * 获取哈希表中元素的个数，是所有元素，不是数组元素个数
     *
     * @return 元素个数
     */
    public int size() {
        return this.size;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("[");
        for (Entry<K, V> entry : table) {
            if (entry != null) {
                builder.append(" ").append("[");
                while (entry != null) {
                    builder.append(" ").append(entry.value);
                    entry = entry.next;
                }
                builder.append(" ").append("]");
            } else {
                builder.append(" ").append("null");
            }
        }
        builder.append(" ]");
        return builder.toString();
    }

    /**
     * 打印每个链表的长度，测试用
     *
     * @return 链表长度
     */
    String elementsLength() {
        int[] nums = new int[table.length];
        int num = 0;
        for (int i = 0; i < table.length; i++) {
            Entry<K, V> entry = table[i];
            while (entry != null) {
                num++;
                entry = entry.next;
            }
            nums[i] = num;
            num = 0;
        }
        // boxed是必要的，将基本类型封装为对象，否则collect无法识别
        Map<Integer, Long> collect = Arrays.stream(nums).boxed().collect(Collectors.groupingBy(c -> c, Collectors.counting()));
        return collect.toString();
    }
}
